/*
 * @Author: liusheng
 * @Date: 2022-04-14 21:04:30
 * @LastEditors: liusheng
 * @LastEditTime: 2022-04-14 21:44:08
 * @Description: 剑指 Offer II 029. 排序的循环链表
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 029. 排序的循环链表
给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。

给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。

如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。

如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。

 

示例 1：


 

输入：head = [3,4,1], insertVal = 2
输出：[3,4,1,2]
解释：在上图中，有一个包含三个元素的循环有序列表，你获得值为 3 的节点的指针，我们需要向表中插入元素 2 。新插入的节点应该在 1 和 3 之间，插入之后，整个列表如上图所示，最后返回节点 3 。


示例 2：

输入：head = [], insertVal = 1
输出：[1]
解释：列表为空（给定的节点是 null），创建一个循环有序列表并返回这个节点。
示例 3：

输入：head = [1], insertVal = 0
输出：[1,0]
 

提示：

0 <= Number of Nodes <= 5 * 10^4
-10^6 <= Node.val <= 10^6
-10^6 <= insertVal <= 10^6
 

注意：本题与主站 708 题相同： https://leetcode-cn.com/problems/insert-into-a-sorted-circular-linked-list/
 */

// Definition for a Node.
class Node {
public:
    int val;
    Node* next;

    Node() {}

    Node(int _val) {
        val = _val;
        next = nullptr;
    }

    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};

class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        if (!head)
        {
            head = new Node(insertVal);
            head->next = head;
            return head;
        }
     
        Node * p1 = head;
        Node * p2 = head->next;

        //traverse at most one cycle to get the minimum and maxmum value node
        // p1->next != head check if has been traverse around one cycle
        while (p1->val <= p2->val && p1->next != head)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        //p2 is the minist value node
        Node * minNode = p2;
        //p1 is the max value node
        Node * maxNode = p1;

        // printf("min:%d,max:%d\n",minNode->val,maxNode->val);
        
        Node * node = new Node(insertVal);
        //node is small than the minist or is bigger than max value
        if (insertVal <= minNode->val || insertVal >= maxNode->val)
        {
            maxNode->next = node;
            node->next = minNode;
            return head;
        }

        //start from min value node
        Node * pre = maxNode;
        Node * p = minNode;
        int curVal = p->val;
        while (insertVal > curVal)
        {
            pre = p;
            p = p->next;
            curVal = p->val;
        }
        
        pre->next = node;
        node->next = p;

        return head;
    }
};

//optimize the above solution
//same as above solution thought
class Solution2 {
public:
    Node* insert(Node* head, int insertVal) {
        if (!head)
        {
            head = new Node(insertVal);
            head->next = head;
            return head;
        }

        Node * cur = head;

        //traverse in one cycle to find the insert point
        while (cur->next != head)
        {
            //min Node max Node split point
            //cur->next is the minist value node
            //cur is the maxmum value node
            if (cur->next->val < cur->val)
            {
                //if insertVal small than minist node or bigger than maxmum node value
                //the cur(maximum Node) is the insert point
                if (insertVal <= cur->next->val || insertVal >= cur->val)
                {
                    break;
                }
            }
            // cur->next is greater equal  than the cur node value
            //then the cur Node is the point to be inserted
            else if (insertVal >= cur->val && insertVal <= cur->next->val)
            {
                break;
            }

            cur = cur->next;
        }

        //node's next point to cur->next
        // Node * node = new Node(insertVal,cur->next);
        // cur->next = node;

        //equal to above two line
        cur->next = new Node(insertVal,cur->next);

        return head;
    }
};